#pragma once
#include "TArray.h"
#include "SString.h"
#include "DString.h"




template< class TKey, class TVal> 
class TMap
{
public:
	struct Pair
	{
		s32_t	Next;
		TKey	Key;
		TVal	Val;

		Pair(){}
		Pair( TKey key, TVal val)
			:Key( key), Val( val)
		{}
	};

	TMap()
		:mHashIndex( 0)
		,mHashCount( 8 )
	{}

	TMap( const TMap& other )
		:mPairs( other.mPairs )
		,mHashCount( other.mHashCount )
		,mHashIndex( 0)
	{
		_rehash();
	}

	~TMap()
	{
		Clear();
	}

	TMap& operator=( const TMap& other )
	{
		mPairs     = other.mPairs;
		mHashCount = other.mHashCount;
		_rehash();
		return *this;
	}

	void Clear( s32_t slk = 0)
	{
		_check( mHashCount);
		mPairs.Clear( slk);
		mHashCount = 8;
		_rehash();
	}


	s32_t Num()
	{
		return mPairs.Num();
	}

	void Set( TKey const& key, TVal const& val)
	{
		if(!mHashIndex)
			_rehash();

		for( s32_t i= mHashIndex[_hashKey( key, mHashCount) ]; 
			i != null_index; i= mPairs[i].Next )
		{
			if( mPairs[i].Key == key )
			{
				mPairs[i].Val = val; 
				return;
			}
		}
		
		_add( key, val );
	}

	bool Remove( TKey const& key)
	{
		s32_t *ptrToIndexToRemoveItem = &mHashIndex[ _hashKey( key, mHashCount)];
		for( ; (*ptrToIndexToRemoveItem != null_index )&& (mPairs[*ptrToIndexToRemoveItem].Key != key); 
			ptrToIndexToRemoveItem = &mPairs[*ptrToIndexToRemoveItem].Next)
		{
		}

		if( *ptrToIndexToRemoveItem == null_index)
		{
			return 0;
		}

		s32_t removeItemIndex = *ptrToIndexToRemoveItem;

		if( mHashCount>(mPairs.Num()-1)*2+8 )
		{
			mHashCount /= 2;
			mPairs.RemoveAt( removeItemIndex);
			_rehash();
			return 1;
		}

		*ptrToIndexToRemoveItem = mPairs[removeItemIndex].Next;

		// if end array item, pop is ok.
		s32_t endIndex = mPairs.Num() - 1;
		if( removeItemIndex == endIndex)
		{
			mPairs.Pop();
			return 1;
		}

		mPairs[ removeItemIndex] = mPairs.Pop();


		s32_t *ptrToSwapItem = &mHashIndex[ _hashKey( mPairs[removeItemIndex].Key, mHashCount)];
		for( ;*ptrToSwapItem != endIndex; ptrToSwapItem = &mPairs[*ptrToSwapItem].Next)
		{}

		_check( *ptrToSwapItem != null_index);

		*ptrToSwapItem = removeItemIndex;
		return 1;

	}


	TVal* Find( const TKey& key )
	{
		if(mHashIndex)
		{
			for( s32_t i= mHashIndex[_hashKey(key, mHashCount) ]; 
				i != null_index; i= mPairs[i].Next )
			{
				if( mPairs[i].Key == key )
				{
					return &mPairs[i].Val;
				}
			}
		}
		return null_ptr;
	}

	const TVal* Find( const TKey& key ) const
	{
		if(mHashIndex)
		{
			for( s32_t i= mHashIndex[_hashKey(key, mHashCount) ]; 
				i != null_index; i= mPairs[i].Next )
			{
				if( mPairs[i].Key == key )
				{
					return &mPairs[i].Val;
				}
			}
		}
		return null_ptr;
	}



	class Iterator
	{
	public:
		Iterator( TMap& map ) : mMap( map ), mPairs( map.mPairs ), mIndex( 0 ), mRemoved(0) {}
		~Iterator() { if( mRemoved ) mMap._relax(); }
		void RemoveCurrent() { mPairs.RemoveAt( mIndex--); ++mRemoved; }
		operator bool () const { return mIndex<mPairs.Num(); }
		TKey& Key(){ return mPairs[mIndex].Key; }
		TVal& Val(){ return mPairs[mIndex].Val; }
		void MoveNext(){ ++mIndex; }
	private:
		TMap& mMap;
		TArray<Pair>& mPairs;
		s32_t mIndex;
		s32_t mRemoved;
	};

	
	void _rehash()
	{
		_check( mHashCount);

		s32_t* newHash = (s32_t*)coreAlloc( sizeof( s32_t) * mHashCount);

		for( s32_t i=0; i<mHashCount; ++i )
		{
			newHash[i] = null_index;
		}
	
		for( s32_t i=0; i<mPairs.Num(); ++i )
		{
			Pair& pair = mPairs[i];
			s32_t hashKey = _hashKey( pair.Key, mHashCount);
			pair.Next  = newHash[hashKey];
			newHash[ hashKey] = i;
		}

		if( mHashIndex )
			coreFree( mHashIndex);

		mHashIndex = newHash;
	}


	void _relax()
	{
		while( mHashCount>mPairs.Num()*2+8 )
			mHashCount /= 2;
		_rehash();
	}

	void _add( TKey const& key, TVal const& val)
	{
		Pair& pair = mPairs.AddNew();
		pair.Key = key;
		pair.Val = val;

		u32_t hashKey  = _hashKey(key, mHashCount);
		pair.Next = mHashIndex[hashKey];

		mHashIndex[hashKey]   = mPairs.Num()-1;

		if( mHashCount *2 + 8 < mPairs.Num() )
		{
			mHashCount *= 2;
			_rehash();
		}
	}

	TArray< Pair> mPairs;
	s32_t *mHashIndex;
	s32_t mHashCount;

};